package 二分查找;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author : ZhuQi
 * @version : 时间:2022/8/11 11:00 版本:
 * 二分查找
 */
public class Demo {

    private static int[] array;

    /**
     * 测试内容:
     * 测试结果:
     */
    @BeforeEach
    public void beforeAll() {
        array = new int[]{1, 3, 5, 7, 9, 10, 8, 6, 4, 2, 0};
    }

    /**
     * 测试内容: 二分查找
     * 思路: 数组前提是有序，然后元素能比较
     * 定义三个指针，一个指向头，一个指向尾，一个指向中间，从中间开始比较，数组中的元素
     * 大于查找的元素中间指针向左偏移，反而小于向右偏移，直到找到或者中间指针超出最小或者最大下标。
     */
    @Test
    public void test01() throws Exception {
        int num = 4;
        int index = 0;
        Arrays.sort(array);
        System.out.println("数组大小:" + array.length);
        System.out.println("需要查找的数:" + num);
        int min = 0, max = array.length - 1, mid = (min + max) / 2;
        while (true) {
            if (mid > max || mid < min) {
                index = -1;
                break;
            } else if (array[mid] == num) {
                index = mid;
                break;
            } else if (array[mid] > num) {
                mid -= 1;
            } else if (array[mid] < num) {
                mid += 1;
            }
        }
        try {
            System.out.println("找到的数：" + array[index]);
        } catch (Exception e) {
            System.out.println("没有找到值");
        }
    }

    /**
     * 测试内容: 二分查找
     * 测试结果: 同样定义三个指针，不同的是，元素比较时调整最小或者最大指针的位置。
     */
    @Test
    public void test02() throws Exception {
        int num = 15;
        int index = -1;
        Arrays.sort(array);
        System.out.println("数组大小:" + array.length);
        System.out.println("需要查找的数:" + num);
        int min = 0, max = array.length - 1, mid;
        while (min <= max) {
            mid = (min + max) / 2;
            if (array[mid] == num) {
                index = mid;
                break;
            } else if (array[mid] < num) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        try {
            System.out.println("找到的数：" + array[index]);
        } catch (Exception e) {
            System.out.println("没有找到值");
        }
    }


    /**
     *
     */
    @Test
    public void test03() throws Exception {
        int num = 4;
        int index = -1;
        Arrays.sort(array);
        System.out.println("数组大小:" + array.length);
        System.out.println("需要查找的数:" + num);
        int min = 0, max = array.length - 1, mid;
        while (min <= max) {
            mid = (min + max) / 2;
            if (array[mid] == num) {
                index = mid;
                break;
            } else if (array[mid] > num) {
                max = mid;
            } else {
                min = mid;
            }
        }
        try {
            System.out.println("找到的数：" + array[index]);
        } catch (Exception e) {
            System.out.println("没有找到值");
        }
    }

    /**
     * 测试内容:
     * 测试结果:
     */
    @Test
    public void testArraysSort() throws Exception {
        Arrays.sort(array);
    }
}
